import java.util.Arrays;

/**
 * @ClassName:
 * @author:
 * @Description:
 * @Date
 **/
public class QuickSort {
    private QuickSort() {
    }

    public static <E extends Comparable<E>> void sort(E[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    public static <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int partition = partition(arr, l, r);
        sort(arr, l, partition - 1);
        sort(arr, partition + 1, r);
    }

    //分区 首先需要知道分区后标定点左边的数要比标定点小，标定点右边的数要比标定点大
    public static <E extends Comparable<E>> int partition(E[] arr, int l, int r) {
        //arr[l+1---j]<v   arr[j+1---i]>v
        //作为标定点
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            //每循环一次，判断标定点的数值和arr[i]的大小
            if (arr[i].compareTo(arr[l]) < 0) {
                //如果arr[i]比标定点的值小
                //先把左半边分区扩大一个位置，j右移
                j++;
                //把j位置的元素和i位置的元素互换，使得比j小的元素落在l+1---j的区间里
                swap(arr, i, j);
            }
        }
        //走完上面的循环，j走到了比标定点小的最后一个元素的位置，此时交换位置，标定点的左边的元素就都比标定点小了，此时就可以返回标定点了
        swap(arr, l, j);
        return j;
    }

    private static <E> void swap(E[] arr, int i, int j) {
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int n = 1000000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
        Integer[] arr2 = Arrays.copyOf(arr, arr.length);
        SortingHelper.sortTest("MergeSort", arr);
        SortingHelper.sortTest("QuickSort", arr2);
    }
}
